package org.zhs.sort;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 选择排序
 * 思想： 每次遍历找到除上次之外的最小值，放到当前位置
 *
 * [5,2,8,9,1]
 * 第一趟遍历： [1,5,8,9,2]
 * 第二趟遍历： [1,2,8,9,5]
 * 第三趟遍历： [1,2,5,8,9]
 * 第四趟遍历: [1,2,5,8,9]
 *
 *
 * 选择排序与冒泡的排序的区别（只讨论基本思想和交换次数）：
 * 一、基本思想
 * 冒泡排序：通过重复地遍历要排序的数列，每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。经过多次遍历，将最大（或最小）的元素逐步 “冒泡” 到数列的一端。
 * 选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
 *
 * 二、交换次数
 * 冒泡排序：在最坏情况下，需要进行多次比较和交换操作。如果数列的初始状态是逆序的，那么每一次比较都可能导致交换。
 * 选择排序：每一趟只进行一次交换，即找到最小（或最大）元素后与当前位置的元素进行交换。
 *
 *
 */
public class SelectionSort {


    public static void main(String[] args) {
        int[] array = IntStream.generate(() -> new Random().nextInt(100)).limit(20).toArray();
        System.out.println("before sorted :" + Arrays.stream(array).boxed().collect(Collectors.toList()));

        for (int outerIndex = 0; outerIndex < array.length; outerIndex++) {
            // 创建一个代表最小元素的索引变量
            int minIndex = outerIndex;
            for (int innerIndex = outerIndex + 1; innerIndex < array.length; innerIndex++) {
                // 将找到的小的那个元素的索引赋值
                if (array[minIndex] > array[innerIndex]) {
                    minIndex = innerIndex;
                }
            }
            // 交换元素
            int temp = array[outerIndex];
            array[outerIndex] = array[minIndex];
            array[minIndex] = temp;
        }

        System.out.println("after sorted :" + Arrays.stream(array).boxed().collect(Collectors.toList()));
    }

}
